package 剑指offer.demo4;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

//https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?
/*
先把根放进队列，然后出队时把他添加到数组，再判断根是否有左右子树进行操作
 */
public class 从上往下打印二叉树 {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        //合法性判断
        if (root == null){
            return new ArrayList<>();
        }
        //定义一个新的动态数组存放层序遍历的节点
        ArrayList<Integer> arrayList = new ArrayList<>();
        //定义一个新的队列操作
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            //把当前节点值插入到数组
            TreeNode cur = queue.poll();
            arrayList.add(cur.val);
            //判断当前节点是否有左右子树,注意这里是当前节点，用的不是递归所以上面要重新把当接节点放在cur
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
        //队列空了说明所有元素添加成功了返回就好了
        return arrayList;
    }
    //题目给定二叉树
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
}
